//链式串
#ifndef __LINKEDSTRING__HPP
#define __LINKEDSTRING__HPP

#include"VirtualString.hpp"

namespace NgSiuKei {

#define KMP

struct linked_string_node {
    char ch;
    linked_string_node *next;
};
#define ls_node linked_string_node

class LinkedString: public VirtualString {
    public:
    LinkedString(void);
    ~LinkedString(void);

    public:
    //清空
    void clear(void);
    //使自身内容等于目标字符串
    void assign(const char * const str);
    //比较大小：self<str返回-1；self=str返回0；self>str返回S1
    int compare(const VirtualString *str) const;
    //拼接
    void concat(const VirtualString *str);
    //获取指定下标（index）开始的指定长度（len）的子串
    VirtualString *getSubstring(const U_L_L index, const U_L_L len) const;
    //获取子串在下标index后出现的位置，否则会抛出异常：EXCEPTION_CAN_NOT_FIND
    U_L_L getIndex(const VirtualString *str, const U_L_L index) const;
    //用str2替换字符串中所有与str1相等的子串
    void replace(const VirtualString *str1, const VirtualString *str2);
    //在指定下标处插入字符串
    void insert(const VirtualString *str, const U_L_L index);
    //在指定下标处删除指定长度的子串
    void remove(const U_L_L index, const U_L_L len);
    //字符串本体
    const char * const getString(void) const;
    //打印
    void print(void) const;

    private:
    ls_node *str;
};

LinkedString::LinkedString(void) {
    this->str = nullptr;
}

LinkedString::~LinkedString(void) {
    this->clear();
}

void LinkedString::clear(void) {
    this->len = 0;
    ls_node *currentChar = nullptr;
    while(nullptr != this->str) {
        currentChar = this->str;
        this->str = this->str->next;
        delete currentChar;
    }
}

void LinkedString::assign(const char * const str) {
    if(!this->isEmpty()) {
        this->clear();
    }
    
    //获取字符串长度
    U_L_L len = 0;
    U_L_L i;
    for(i=0; '\0' != str[i]; ++i) {
        len++;
    }

    ls_node *currentChar = nullptr;
    ls_node *newChar = nullptr;
    if(len > 0) {
        //第一个字符（其实在循环里多加一个判断就不用搞这一步了，但是我现在不喜欢这么多判断）
        newChar = new ls_node;
        newChar->ch = str[0];
        newChar->next = nullptr;
        this->str = newChar;
        currentChar = newChar;
        //后面的字符
        for(i=1; i<len; ++i) {
            newChar = new ls_node;
            newChar->ch = str[i];
            newChar->next = nullptr;

            currentChar->next = newChar;
            currentChar = currentChar->next;
        }
    }
    this->len = len;
}

int LinkedString::compare(const VirtualString *str) const {
    char charA, charB;
    const U_L_L len = str->getLen();
    const char * const charStr = str->getString();
    ls_node *currentChar = this->str;
    U_L_L i = 0;

    while(nullptr != currentChar && i < len) {
        charA = currentChar->ch;
        charB = charStr[i];
        if(charA < charB) {
            return -1;
        }
        else if(charA > charB) {
            return 1;
        }
        currentChar = currentChar->next;
        i++;
    }
    if(len == this->len) {
        return 0;
    }
    else if(this->len < len) {
        return -1;
    }
    else {
        return 1;
    }
}

void LinkedString::concat(const VirtualString *str) {
    const U_L_L len = str->getLen();
    const char * const charStr = str->getString();
    ls_node *currentChar = this->str;
    ls_node *newChar = nullptr;

    if(len > 0) {
        U_L_L i = 0;
        if(nullptr == this->str) {//本身字符串长度为0
            newChar = new ls_node;
            newChar->ch = charStr[0];
            newChar->next = nullptr;
            this->str = newChar;
            currentChar = newChar;
            i = 1;
        }
        else {//本身字符串长度不为0，遍历到串最后一个字符
            while(nullptr != currentChar->next) {
                currentChar = currentChar->next;
            }
        }

        while(i < len) {
            newChar = new ls_node;
            newChar->ch = charStr[i];
            newChar->next = nullptr;

            currentChar->next = newChar;
            currentChar = currentChar->next;
            
            i++;
        }

        this->len += len;
    }
}

VirtualString *LinkedString::getSubstring(const U_L_L index, const U_L_L len) const {
    if(index >= this->len) {
        throw EXCEPTION_OUT_OF_BOUNDS;
    }
    if(index+len-1 >= this->len) {
        return nullptr;
    }

    U_L_L i;
    //定位到对应下标
    ls_node *currentChar = this->str;
    for(i=0; i<index; ++i) {
        currentChar = currentChar->next;
    }

    char *charSubstring = new char[len+1];
    for(i=0; i<len; ++i) {
        charSubstring[i] = currentChar->ch;
        currentChar = currentChar->next;
    }
    charSubstring[len] = '\0';

    //生成对象
    LinkedString *substring = new LinkedString;
    substring->assign(charSubstring);

    return substring;
}

U_L_L LinkedString::getIndex(const VirtualString *str, const U_L_L index) const {
    if(index >= this->len || index+str->getLen() > this->len) {
        throw EXCEPTION_OUT_OF_BOUNDS;
    }

    const U_L_L len = str->getLen();
    const char * const charStr = str->getString();

#ifndef KMP
    //使用朴素匹配

    U_L_L i;
    //定位到对应下标
    ls_node *currentChar = this->str;
    for(i=0; i<index; ++i) {
        currentChar = currentChar->next;
    }

    //开始匹配
    U_L_L resultIndex = index;
    ls_node *tempChar = nullptr;
    while((nullptr != currentChar) && (resultIndex <= this->len-len)) {
        tempChar = currentChar;
        for(i=0; (i < len) && (nullptr != tempChar); ++i) {
            if(tempChar->ch != charStr[i]) {
                break;
            }
            else if(len-1 == i) {
                return resultIndex;
            }
            tempChar = tempChar->next;
        }
        currentChar = currentChar->next;
        resultIndex++;
    }

#else
    //使用KMP模式匹配

    //先计算next数组
    unsigned int next[len];
    next[0] = 0;
    U_L_L preLen = 0;//前缀长度
    U_L_L i = 1;
    while(i<len) {
        if(charStr[i] == charStr[preLen]) {
            preLen++;
            next[i] = preLen;
            i++;
        }
        else {
            if(0 == preLen) {
                next[i] = 0;
                i++;
            }
            else {
                preLen = next[preLen-1];
            }
        }
    }
    
    //定位到对应下标
    ls_node *currentChar = this->str;
    for(i=0; i<index; ++i) {
        currentChar = currentChar->next;
    }//在此之后i=index
    
    //再遍历查找子串下标
    U_L_L j=0;//用于遍历子串的下标
    while(nullptr != currentChar) {
        if(currentChar->ch == charStr[j]) {
            if(len-1 == j) {
                return i-j;
            }
            i++;
            j++;
            currentChar = currentChar->next;
        }
        else if(j>0) {
            j = next[j-1];
        }
        else {
            i++;
            currentChar = currentChar->next;
        }
    }
    
#endif

    throw EXCEPTION_CAN_NOT_FIND;
}

void LinkedString::replace(const VirtualString *str1, const VirtualString *str2) {
    if(this->isEmpty()) {
        throw EXCEPTION_IS_EMPTY;
    }
    if(nullptr == str1 || nullptr == str2) {
        throw EXCEPTION_NULL_POINTER;
    }
    if(str1->isEmpty()) {
        throw EXCEPTION_NULL_POINTER;
    }

    const U_L_L len = str1->getLen();

    //为了防止str1和str2就是this，生成一个临时字符串
    LinkedString *strTemp1 = new LinkedString;
    LinkedString *strTemp2 = new LinkedString;
    strTemp1->assign(str1->getString());
    strTemp2->assign(str2->getString());

    //因为链表不存在大量的数组内存分配销毁问题，所以我直接用getIndex、insert、remove三个函数实现
    try {
        U_L_L index = 0;
        while(true) {
            index = this->getIndex(strTemp1, index);//使用不用0作为参数主要是怕删除子串后前后拼起来又形成了新的str1子串
            this->remove(index, len);
            this->insert(strTemp2, index);
            index += strTemp2->len;
        }
    }
    catch(Exception &e) {
        return;
    }
}

void LinkedString::insert(const VirtualString *str, const U_L_L index) {
    if(index > this->len) {
        throw EXCEPTION_OUT_OF_BOUNDS;
    }

    const char * const newCharStr = str->getString();
    const U_L_L len = str->getLen();
    if(0 == len) {
        return;
    }

    //定位到index前一个节点
    ls_node *preChar = this->str;
    U_L_L i;
    for(i=1; i<index; ++i) {
        preChar = preChar->next;
    }

    //生成一条链式字符串
    ls_node *firstChar = nullptr;
    ls_node *endChar = nullptr;
    ls_node *newChar = nullptr;
    ls_node *currentChar = nullptr;
    for(i=0; i<len; ++i) {
        newChar = new ls_node;
        newChar->ch = newCharStr[i];
        newChar->next = nullptr;
        if(nullptr == currentChar) {
            currentChar = newChar;
        }
        else {
            currentChar->next = newChar;
            currentChar = currentChar->next;
        }

        if(0 == i) {
            firstChar = currentChar;
        }
        if(len-1 == i) {
            endChar = currentChar;
        }
    }

    //插入
    if(nullptr != firstChar && nullptr != endChar) {
        if(this->len == 0) {
            this->str = firstChar;
        }
        else {
            endChar->next = preChar->next;
            preChar->next = firstChar;
        }
        this->len += len;
    }
}

void LinkedString::remove(const U_L_L index, const U_L_L len) {
    if(index >= this->len || index+len-1 >= this->len) {
        throw EXCEPTION_OUT_OF_BOUNDS;
    }

    if(0 == len) {
        return;
    }

    U_L_L i;
    ls_node *firstChar = nullptr;
    ls_node *endChar = nullptr;

    if(index > 0) {
        //定位到index前一个节点
        ls_node *preChar = this->str;
        for(i=1; i<index; ++i) {
            preChar = preChar->next;
        }

        firstChar = preChar->next;
        endChar = preChar;
        //移动到待删除字符串的最后一个字符
        for(i=0; i<len; ++i) {
            endChar = endChar->next;
        }

        //删除
        preChar->next = endChar->next;
    }
    else {
        //定位待删除子串的头尾节点
        firstChar = this->str;
        endChar = firstChar;
        for(i=1; i<len; ++i) {
            endChar = endChar->next;
        }

        //删除
        this->str = endChar->next;
    }
    this->len -= len;

    //删除子串
    ls_node *deleteChar = nullptr;
    endChar->next = nullptr;
    while(nullptr != firstChar) {
        deleteChar = firstChar;
        firstChar = firstChar->next;
        delete deleteChar;
    }
}

const char * const LinkedString::getString(void) const {
    char *str = new char[this->len+1];
    ls_node *currentChar = this->str;
    for(U_L_L i=0; i<this->len; ++i) {
        str[i] = currentChar->ch;
        currentChar = currentChar->next;
    }
    str[this->len] = '\0';
    return str;
}

void LinkedString::print(void) const {
    cout << this->getString() << endl;
}

}

#endif